The present invention relates generally to the storage of data in a device, and more particularly to a method and apparatus for reducing memory storage requirements in an output display device.
A computer system can output data to a wide variety of output display devices. Output display devices such as laser printers, plotters, and other printing devices produce an image or xe2x80x9cvisual representationxe2x80x9d onto a sheet of paper or the like, while output display devices such as computer monitors develop visual representations on a computer screen.
Many output display devices receive display data in the form of a xe2x80x9cbitmapxe2x80x9d or xe2x80x9cpixel mapxe2x80x9d and generate visual representations from the display data. A pixel is a fundamental picture element of a visual representation generated by a display device, and a bitmap is a data structure including information concerning a number of pixels of the representation. Bitmaps that contain more than on/off information are often referred to as xe2x80x9cpixel maps.xe2x80x9d As used herein, both bitmaps and pixel maps are referred to as xe2x80x9cbitmaps.xe2x80x9d
A printer can print dots on a piece of paper corresponding to the information of a bitmap. Alternatively, a computer monitor can illuminate pixels based upon the information of the bitmap. A xe2x80x9crasterxe2x80x9d output device creates a visual representation by displaying the array of pixels arranged in rows and columns from the bitmap. Many output devices are raster output devices. Typically, a xe2x80x9cpagexe2x80x9d of pixels corresponding to a printed or displayed page is received and stored in memory before the pixels are displayed by the output display device.
A visual representation can contain a number of image types, including text, graphics, photographic images, and so on. Data of these types can be efficiently stored in files with other image information as high level xe2x80x9cobjects.xe2x80x9d An xe2x80x9cobject,xe2x80x9d as referred to herein, is the data and attributes defining a particular visual representation. The objects can be edited or otherwise manipulated using an application program (xe2x80x9csoftwarexe2x80x9d) running on a computer. When displaying the objects with an output display device such as a printer or display screen, the objects are typically first rasterized (or xe2x80x9crenderedxe2x80x9d) into bitmaps. The output display device stores display bitmap data in memory before displaying a page of data.
A problem in the prior art methods of providing bitmaps to output display devices is that a large amount of storage space is required to store the bitmap before it is displayed. Storage space requirements have increased as the demand for high-resolution representations with more realistic attributes has become more prominent. For example, using a laser printer capable of printing black-and-white bitmaps at a resolution of 600 dots per inch (dpi), a typical displayed page (8.5xc3x9711 inches) requires about 3.8xc3x97106 bytes of memory. When printing a page of color pixels, for example, having 4 colors per pixel and 8 bits per color, the memory requirement increases to about 121xc3x97106 bytes of memory. With such memory requirements, a significant portion of the cost of manufacturing an output display device capable of processing one or more pages such as a laser printer is the cost of the required memory.
A method that has been used to reduce the memory requirements for displaying high-resolution images involves the compression of the bitmap data according to a compression method or algorithm. A compression algorithm can significantly reduce the space needed to store bitmaps by removing redundancy. Some compression algorithms are xe2x80x9clossless,xe2x80x9d meaning that they compress data and reduce storage requirements with no loss of information. This type of compression is often used with text objects and the like, since bitmaps of text objects typically contain considerable redundancy allowing for significant compression. Lossless compression techniques are ideal for text objects because any loss of information during the compression and subsequent decompression processes would adversely affect appearance and legibility of the text. Other types of compression algorithms are xe2x80x9clossy,xe2x80x9d meaning that they compress data with some loss of information. These types of compression algorithms are typically used with image bitmap data, photographs and the like, since the loss of information can often be unnoticeable in a high resolution image.
When the compressed bitmap is to be displayed, it is decompressed using a corresponding decompression algorithm and sent to a print engine, monitor, or other output display device.
The present invention provides a method and apparatus for compressing a two-dimensional image. A method of compressing a two-dimensional image represented as a raster of pixels. The method includes receiving a sequence of the pixels in raster order; and defining a first match pixel location and a second match pixel location relative to a current pixel location in the raster, a first match pixel being the pixel at the first match pixel location relative to the current pixel, a second match pixel being the pixel at the second match pixel location relative to the current pixel, where the first pixel location and the second pixel location are not contiguous in the sequence. Each pixel in the sequence is considered in turn as the current pixel. The method then includes comparing the current pixel only to the first match pixel and the second match pixel and then encoding the value of the current pixel if the value of the current pixel does not match the value of the first match pixel or the value of the second match; and otherwise if the value of the current pixel matches the value of the first match pixel then encoding the current pixel as a first token where the first token includes a reference to the first match pixel and a length and where the length is determined based on a number of consecutive pixels relative to the current pixel whose values match the values of similarly located pixels relative to the first match pixel; or if the value of the current pixel matches the value of the second match pixel then encoding the current pixel as a second token where the second token includes a reference to the second match pixel and a length and where the length is determined based on a number of consecutive pixels relative to the current pixel whose values match the values of similarly located pixels relative to the second match pixel.
Aspects of the invention can include one or more of the following features. The previous pixel can be the pixel immediately previous in the current scan line or a last pixel in an immediately previous scan line if the current pixel is the first pixel in the current scan line. The located pixel can be positioned in an immediately previous scan line above the current scan line and directly above the current pixel or positioned adjacent to a pixel in the immediately previous scan line and above the current pixel.
The length can be unbounded.
The method can include encoding the length including storing a code and a value. The code can be representative of a range of length values that are encoded and the value indicative of an exact length value within the range. The method can include gathering statistical data during the compression process and re-encoding the image. Tokens can be classified into groups and statistical data can be gathered on how often each token group type is used.
The method can include gathering statistical data for a number of encoded tokens having lengths falling within each of a number of predetermined ranges of lengths.
The pixel value can be encoded as a literal if the pixel value does not match the previous or located pixel value. The encoding of a literal can include encoding the value of the current pixel in accordance with a predefined mathematical algorithm operating on the value of the current pixel value. The mathematical algorithm can include determining a distance between the current pixel value and a value of a pixel immediately preceding the current pixel in the current scan line and encoding the distance.
In another aspect, the invention provides a method of compressing a two-dimensional image. The two-dimensional image is divided into a sequence of scan lines where each scan line includes a sequence of pixels and where each pixel has an associated value representative of a shade to be rendered when displaying the two-dimensional image on a raster output device. The method includes processing pixels in raster order including, for each pixel in a current scan line, comparing a pixel value of a current pixel with values of a plurality of previously processed pixels in the current or previous scan lines. If a match is detected, then the method includes encoding the current pixel as a copy of a matching pixel in the current or previous scan line and a length where the length is determined based on a number of consecutive pixels after the current pixel that satisfy a matching criterion. The matching criterion is defined by a relationship between the current pixel and the matching pixel. If the value of the current pixel does not match the value of the matching pixel(s) then the pixel value is encoded.
In another aspect, the invention provides a method of generating a compressed representation of a two-dimensional image where the image is described as a sequence of pixels in raster order. The method includes receiving the two-dimensional image as a sequence of pixels in raster order. For each pixel, the method includes determining whether the pixel is part of a first string of pixels that is identical to a second string of pixels found previously in the image at one of a plurality of preselected fixed distances from the first string of pixels. If so, the first string of pixels is encoded as a reference to the second string of pixels. Otherwise, the pixel is encoded.
Aspects of the invention can include one or more of the following features. One of the preselected fixed distances can be one pixel, thereby allowing a first string of pixels to be encoded as being identical to a second string of pixels that occurred one pixel earlier in the two-dimensional image. One of the preselected fixed distances can be a length of one scan line of the two-dimensional image, thereby allowing a first string of pixels to be encoded as being identical to a second string of pixels that occurred directly above the first string of pixels on the previous scan line. The number of preselected fixed distances can be two. One of the preselected fixed distances can be one plus a length of one scan line of the image, thereby allowing a first string of pixels to be encoded as being identical to a second string of pixels that occurred on the previous scan line, one pixel to the left of the first string of pixels. The number of preselected fixed distances can be fewer than a maximum of the preselected fixed distances. A maximum length of a first string of pixels that may be encoded can be unbounded.
The step of encoding the pixel as a reference to the second string of pixels can include encoding the pixel as a token. The token can be encoded using a reference to a previous pixel and a length. The token can be encoded based on one or more previously encoded tokens immediately preceding a current token. The current token can include only length data. A value for all pixels in a string encoded by the current token can be derived by evaluating one or more previous tokens.
The method can include encoding a single pixel as a ranking based on a distance of its value from the value of a previous pixel. The step of encoding the first string of pixels as a reference to the second string of pixels can include dividing tokens into groups and encoding a token by encoding its group and encoding the particular token within a given group with a code. The token within a group code can be variable length.
In another aspect, the invention provides a method of generating a compressed representation of a two-dimensional image as a sequence of encoded tokens. Each token represents either a first string of pixels that is identical to a second string of pixels that occurs previously in the image or a single encoded pixel value. The image is in the form of an uncompressed representation and includes a sequence of pixels in raster order. The method includes receiving the sequence of pixels and for each pixel, determining whether the pixel is part of a first string of pixels that is identical to a second string of pixels found previously in the image at one of a plurality of preselected fixed distances from the first string of pixels. If so, the pixel is encoded in the first string of pixels. Otherwise, the pixel is encoded.
In another aspect, the invention provides a method of generating an uncompressed representation of a two-dimensional image as a sequence of pixels in raster order (given a compressed representation of the image as a sequence of encoded tokens where each token represents either a first string of pixels that is identical to a second string of pixels that occurs previously in the uncompressed representation of the image or single encoded pixel value). The method includes sequentially retrieving the encoded tokens and decoding each encoded token. If a token represents a first string of pixels, the first string is outputted by copying a second string of pixels specified by the token. Otherwise, a particular pixel specified by the token is outputted.
In another aspect, the invention provides a digital output processing system with object compression and decompression for processing a two-dimensional image. The system includes a rasterizer which converts data objects into bitmap objects and a compressor operable to receive the bitmap objects as a sequence of pixels in raster order and for each pixel: determine whether the pixel is part of a first string of pixels that is identical to a second string of pixels found previously in the two-dimensional image at one of a plurality of preselected fixed distances from the first string of pixels, if so, encoding the first string of pixels as a reference to the second string of pixels, and otherwise, encoding the pixel. The system includes a decompressor which decompresses the compressed bitmap objects.
Aspects of the invention can include one or more of the following features. The compressor and decompressor can be implemented in an output device. The output device can be one of the group consisting of a printer device and a screen display. The system can include a mechanism for dividing the bitmap objects into nonintersecting regions, wherein the compressor compresses the regions.
Implementations of the invention can include one or more of the following advantages. Object data can be compressed using two or more types of tokens. The compression process can include entropy encoding techniques for optimizing the compression for a typical page or the compression can selectively be optimized for the particular page being compressed using a two part compression process. In the first pass, tokens are generated based on the data to be compressed while statistics are gathered about the particular page being compressed. At the end of the first pass, the resultant product is a compressed bitmap and information describing how much more compressed the bitmap could be using the statistics information. The process can end after the first pass or improvements to the compression can be realized by invoking a second pass. In a second pass, the tokens can be re-encoded using entropy encoding techniques to optimize the encoding for the particular page of content. This permits a dramatic reduction in memory space requirements with no loss of image quality. With less memory requirements for storing displayed data, the cost to produce an output display device can be drastically decreased. In addition, the compressed data can be easily decoded in real time to support printing operations.